//435 不重叠区间
/*
给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠
输入输出样例：
- 输入是一个数组，数组由多个长度固定为 2 的数组组成，表示区间的开始和结尾。输出一个整数，表示需要移除的区间数量
- Input: [[1,2], [2,4], [1,3]]  移除[1,3]，使得剩余的区间互不重叠
  Output: 1

分析：
- 选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。优先保留结尾小且不相交的区间。先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间
*/
int eraseOverlapIntervals(vector<vector<int>> &intervals)
{
	if (intervals.empty())
	{
		return 0;
	}
	int n = intervals.size();
	//排序
	sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) {
		return a[1] < b[1]; //对每个vector的第二个元素进行排序，即区间的结尾
	});
	int total = 0, prev = intervals[0][1]; //prev存放区间结尾数字
	for (int i = 1; i < n; ++i)
	{
		if (intervals[i][0] < prev) //从第二个区间的开头与第一个区间结尾开始对比
		{
			++total;
		}
		else
		{
			prev = intervals[i][1];
		}
	}
	return total;
}
